package main

import "sort"

//func maxSatisfaction(satisfaction []int) int {
//	sort.Ints(satisfaction)
//	// 有没有必要舍去某些菜要看期望值是否为正
//	n := len(satisfaction)
//	start := 0
//	sum := 0
//	// 如果第一项就大于0，就不用判断了
//	if satisfaction[start] >= 0 {
//		for i := 1; i <= n; i++ {
//			sum += i * satisfaction[i-1]
//		}
//		return sum
//	}
//	//如果最后一项都小于等于0，那也不用判断了
//	if satisfaction[n-1] <= 0 {
//		return 0
//	}
//	// \
//	i := 0
//	j := n - 1
//	var exp int
//	for satisfaction[i] <= 0 {
//		exp = exp + (i+1)*satisfaction[i] + n*satisfaction[j]
//		if exp < 0 {
//			start++
//			i = start
//			n--
//			exp = 0
//		}
//		i++
//		j--
//	}
//	for i := 1; i <= n-start-1; i++ {
//		sum += i * satisfaction[start]
//		start++
//	}
//	return sum
//}

func maxSatisfaction(satisfaction []int) int {
	sort.Slice(satisfaction, func(i, j int) bool {
		return satisfaction[i] > satisfaction[j]
	})
	presum, ans := 0, 0
	for _, si := range satisfaction {
		if presum+si > 0 {
			presum += si
			ans += presum
		} else {
			break
		}
	}
	return ans
}

func main() {
	maxSatisfaction([]int{-1, -8, 0, 5, -7})
}
